Java Random安全性分析

简介

Java的Random类是最常用的一种随机数生成类，可以满足绝大部分场景的使用，但其并不能满足安全性方面的需求。

本文根据第三届强网杯一道密码学题目对其安全性进行分析。如果可以得到随机数生成器的第一个到第二个随机数，那么可以很容易的预测到此后的随机数。

问题

原题大致如下：

主要python代码：

for i in range(200):
    o = subprocess.check_output(["java", "Main"])
    tmp=[]
    for i in o.split("\n")[0:3]:
        tmp.append(int(i.strip()))
    v1=tmp[0] % 0xffffffff
    v2=tmp[1] % 0xffffffff
    v3=tmp[2] % 0xffffffff
    print "[-]"+str(v1)
    print "[-]"+str(v2)
    v3_get=int(raw_input("[-]"))
    if v3_get==v3:
        print "[++++++++++++++++]challenge 2 completed[++++++++++++++++]"
        return
    else:
        print "[+]failed"

主要java代码：

public class Main {
  public static void main(String[] paramArrayOfString) {
    Random random = new Random();
    System.out.println(random.nextInt());
    System.out.println(random.nextInt());
    System.out.println(random.nextInt());
  }
}

题目意思比较简单，使用java.util.Random类默认种子生成随机数，请根据前两个随机数预测第三个随机数。

源码分析

由于编程语言生成的随机数都是伪随机数，所以一般而言要预测随机数需要破解其种子seed，而此处使用默认种子，所以先查看Random类源码分析其默认种子。

主要代码如下：

public Random() {  
        this(seedUniquifier() ^ System.nanoTime());  
    }
private static long seedUniquifier() {  
        for (;;) {  
            long current = seedUniquifier.get();
            long next = current * 181783497276652981L;
            if (seedUniquifier.compareAndSet(current, next)) 
                return next;  
        }  
private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);

可以看到默认种子为seedUniquifier() ^ System.nanoTime()，经简单测试可以发现其中seedUniquifier()方法生成的是一个常数，而System.nanoTime()返回的是一个纳秒，但此时间与当前时间无关，只能用于计算时间差，并且其长度很长，暴力破解难度很大。所以要破解默认种子几乎是不可能的。

接下来分析nextInt方法：

public int nextInt() {  
    return next(32);//整型的长度 
}
protected int next(int bits) {  
    long oldseed, nextseed;  
    AtomicLong seed = this.seed;
    do {  
        oldseed = seed.get();  
        nextseed = (oldseed * multiplier + addend) & mask;//线性同余算法  
    } while (!seed.compareAndSet(oldseed, nextseed));  
    return (int)(nextseed >>> (48 - bits));  
}

可以看到nextInt调用了next方法，传递的参数是32，即Java-Int的长度。

再接着分析next方法，其中核心代码为nextseed = (oldseed * multiplier + addend) & mask;，在类定义开头处可以看到：

1
2
3

private static final long multiplier = 0x5DEECE66DL;  
private static final long addend = 0xBL;  
private static final long mask = (1L << 48) - 1;

所以可以知道，新种子是根据旧种子乘以常数multiplier再加上常数addend，最后再取后48位。而while (!seed.compareAndSet(oldseed, nextseed))只是为了保证新旧种子不一致，一般都为true。

最后再将新种子无符号右移16位作为最终的返回值。

预测

所以，如果可以得到两个随机数，那么只需要暴力破解低16位，即可完成预测。

破解思路如下：

先将第一个随机数左移16位作为旧种子，此时种子的低16位为0x0000;
暴力破解低16位，范围为0x0000-0xffff;
暴力破解时每次生成一个新种子并无符号右移16位，判断是否与第二个随机数相等，如果相等则破解成功。

使用java代码生成三个随机数，使用前两个随机数预测第三个，预测的java代码如下：

public class test
{
    private static final long multiplier = 0x5DEECE66DL;  
    private static final long addend = 0xBL;  
    private static final long mask = (1L << 48) - 1;  
    public static void main(String[] paramArrayOfString)
    {
        int a = -117510532;
        int b = -1347210525;
        int c = 2076362838;//待预测值
        long oldseed = ((long)a << 16);
        for (int i=0; i<=0xffff; i++){//暴力破解种子
            long nextseed = (oldseed * multiplier + addend) & mask;
            if ((int)(nextseed >>> 16) == b){
                oldseed = nextseed;
                break;
            }
            oldseed += 1;
        }
        int next_int = (int)(((oldseed * multiplier + addend) & mask) >>> 16);
        assert next_int == c;
    }
}

测试多次可以看到均能正确预测。

此处需要注意的是，由于Java的Int是使用补码形式保存的，48位的long无符号右移16位并转换为int会产生负数，所以如果使用其他语言时需要注意此情况。由于正数补码位其本身，所以当几个随机数均为正数时预测不会有问题；但负数的补码为其绝对值取反再加1，所以需要进行处理。

预测的python3代码如下：

multiplier = 0x5DEECE66D
addend = 0xB
mask = (1 << 48) - 1
def d(n):  # 补码处理
    if bin(abs(n))[2:].zfill(32)[0] == '1':
        n = ((-n) ^ (0xffffffff)) + 1
    return n
a = -117510532
b = -1347210525
c = 2076362838#待预测值
oldseed = a << 16
for i in range(0xffff):#暴力破解种子
    nextseed = (oldseed * multiplier + addend) & mask
    if d(nextseed >> 16) == b:
        oldseed = nextseed
        break
    oldseed += 1
next_int = d(((oldseed * multiplier + addend) & mask) >> 16)
assert next_int == c

此外，还有一点需要注意的是，在进行破解时，可能存在多解的情况，不过由于只需要尝试2^16次，遇到此情况概率不大，故上述代码没有考虑。

其他方法

原题只考察了nextInt方法，但在java.util.Random类中，除了常用的nextInt方法，还有其他几个常用方法，分析结果如下：

nextLong():
1
2
3
public long nextLong() {
return ((long)this.next(32) << 32) + (long)this.next(32);
}
简单分析可以发现，nextLong()生成的随机数是第一个nextInt左移32位再加上第二个nextInt，所以预测nextLong()条件更加简单，只需要知道任意一个随机数即可预测后续的随机数，完全没有任何安全性。

预测的java代码如下：

public class test
{
    private static final long multiplier = 0x5DEECE66DL;  
    private static final long addend = 0xBL;  
    private static final long mask = (1L << 48) - 1;  
    public static void main(String[] paramArrayOfString)
    {
        long a1 = 1711142106566560141L;
        long b1 = 6785139325399845420L;//待预测值
        int a = (int)(a1 >> 32);//取高32位
        int b = (int)(a1 & 0xffffffff);//取低32位
        long oldseed = ((long)a << 16);
        for (int i=0; i<=0xffff; i++){//暴力破解种子
            long nextseed = (oldseed * multiplier + addend) & mask;
            if ((int)(nextseed >>> 16) == b){
                oldseed = nextseed;
                break;
            }
            oldseed += 1;
        }
        long nextseed = (oldseed * multiplier + addend) & mask;
        int next_int = (int)(nextseed >>> 16);
        long nextseed2 = (nextseed * multiplier + addend) & mask;
        int next_int2 = (int)(nextseed2 >>> 16);
        long b2 = ((long)next_int << 32) + (long)next_int2;
        assert b1==b2;
    }
}

nextBoolean():
1
2
3
public boolean nextBoolean() {
return this.next(1) != 0;
}
可以看到这里调用了this.next(1)，也就是将48位的新种子丢弃掉低47位，由于丢弃数据太多，所以无法暴力破解。

nextFloat():

1
2
3

public float nextFloat() {  
        return next(24) / ((float)(1 << 24));
}

可以看出此方法基本与nextInt方法相同，不过是将32位改成了24位，再除以一个常数。

预测的java代码如下：

public class test
{
    private static final long multiplier = 0x5DEECE66DL;  
    private static final long addend = 0xBL;  
    private static final long mask = (1L << 48) - 1;  
    public static void main(String[] paramArrayOfString)
    {
        float a0 = (float)(1 << 24);
        float a1 = (float)0.712306;
        float b1 = (float)0.5084883;
        float c1 = (float)0.8681924;//待预测值
        int a = (int)(a1 * a0);
        int b = (int)(b1 * a0);
        int c = (int)(c1 * a0);
        long oldseed = ((long)a << 24);
        for (int i=0; i<=0xffffff; i++){//暴力破解种子
            long nextseed = (oldseed * multiplier + addend) & mask;
            if ((int)(nextseed >>> 24) == b){
                int next_int = (int)(((nextseed * multiplier + addend) & mask)>>>24);
                if (next_int==c){//可能存在多解
                    assert next_int/a0==c1;
                    break;
                }
            }
            oldseed += 1;
        }
    }
}

这里由于预测空间变成了2^24，存在多解的可能性变大，所以一般需要尝试多次（大约1-3次）才能成功。

nextDouble():

private static final double DOUBLE_UNIT = 1.1102230246251565E-16D;
public double nextDouble() {  
        return (((long)(next(26)) << 27) + next(27)) * DOUBLE_UNIT;
}

可以看出基本上与nextLong方法相似，只是位数上有所区别，并且最终乘以了一个常数。所以依然只需要知道一个随机数即可预测出后续的所有随机数。

预测的java代码如下：

public class test
{
    private static final long multiplier = 0x5DEECE66DL;  
    private static final long addend = 0xBL;  
    private static final long mask = (1L << 48) - 1;
    private static final double DOUBLE_UNIT = 1.1102230246251565E-16D;
    public static void main(String[] paramArrayOfString)
    {
        double a1 = 0.7402471335502712;
        double b1 = 0.010098863202140596;//待预测值
        int a = (int)((long)(a1 / DOUBLE_UNIT)>>27);//取高27位
        int b = (int)((long)(a1 / DOUBLE_UNIT)&((1L << 27) - 1));//取低27位
        long oldseed = ((long)a << 22);
        for (int i=0; i<=((1L<<22)-1); i++){//暴力破解种子
            long nextseed = (oldseed * multiplier + addend) & mask;
            if ((int)(nextseed >>> 21) == b){
                oldseed = nextseed;
                break;
            }
            oldseed += 1;
        }
        long nextseed = (oldseed * multiplier + addend) & mask;
        int next_int1 = (int)(nextseed >>> 22);
        long nextseed2 = (nextseed * multiplier + addend) & mask;
        int next_int2 = (int)(nextseed2 >>> 21);
        double b2 = (((long)(next_int1) << 27) + next_int2) * DOUBLE_UNIT;
        assert b1==b2;
    }
}

除了这几个常用的方法外，java.util.Random类还有一些方法，此处不再分析。

总结

java.util.Random类的默认种子仅与System.nanoTime()有关，而此方法产生的时间与系统当前时间无关，破解难度较大，所以使用默认种子生成的第一个随机数是很难预测到的。

但是对于nextLong和nextDouble方法，只需要知道任意一个随机数即可预测后续随机数；而对于nextInt和nextFloat，如果同时泄漏第一个和第二个随机数，那么后面的随机数也都是可预测的。

在Java中，要使用安全的随机数应该使用java.Security.SecureRandom类，即使使用相同的初始seed，其生成的结果也完全不同，可以满足随机数的不可预测性需求。而其他的如Math.random()和ThreadLocalRandom也都是不安全的，使用时需要特别注意。

参考

Random–阅读源码从jdk开始